function new_game() {
}

/*function make_move() {
   var board = get_board();
	
   // we found an item! take it!
   if (board[get_my_x()][get_my_y()] > 0) {
       return TAKE
   }
   
   var rand = Math.random() * 4;

   if (rand < 1) return NORTH;
   if (rand < 2) return SOUTH;
   if (rand < 3) return EAST;
   if (rand < 4) return WEST;

   return PASS;
}*/

var nearest_fruit_location_x = -5555;
var nearest_fruit_location_y = -5555;
var nearest_fruit_distance = 100000;
var cur_location_x;
var cur_location_y;

var open_squares;
var fruit_count = new Array();

function make_move() {
   var board = get_board();
  
   for(var count = 1; count <= get_number_of_item_types(); count++){
	  fruit_count[count] = get_total_item_count(count) - get_my_item_count(count) - get_opponent_item_count(count);
   }
   
   // we found an item! take it!
   if (board[get_my_x()][get_my_y()] > 0) {
      if(get_my_x() === nearest_fruit_location_x && get_my_y() === nearest_fruit_location_y){
         nearest_fruit_location_x = -5555;
	     nearest_fruit_location_y = -5555;
	     nearest_fruit_distance = 100000;
	  }
	  fruit_count[board[get_my_x()][get_my_y()]]--;
      return TAKE
   }
	
   cur_location_x = get_my_x();
   cur_location_y = get_my_y();
   open_squares = new Array();
   myBot.init_arrays();
   return myBot.find_fruit(cur_location_x, cur_location_y);
}

var myBot = (function(){
   var checked_squares = new Array(HEIGHT);
   var open_squares_grid = new Array(HEIGHT);
   var CHECKED = 1;
   var MARKED_FOR_EXPAND= 1;
   var test_var =1;
   
   function get_min_type(){
	   var min_fruit_type = 1;
	   var min_fruit_count = 1000;
	   var prev_min_fruit_type = 1;
	   for(var count = 1; count <= (fruit_count.length)-1; count++){
		  //check to make sure the number of fruits for "count" type is useful for us
		  if(fruit_count[count]+get_my_item_count(count) >= get_opponent_item_count(count) && 
			 get_my_item_count(count) <= fruit_count[count]+get_opponent_item_count(count)){
			 if(fruit_count[count] < min_fruit_count && fruit_count[count] !== 0){
				min_fruit_count = fruit_count[count];
				min_fruit_type = count;
			 }
		  }
	   }
	   //if none of the fruits are worth going after i.e. it will not help us get more fruits of that type compared to the opponenet
	   if(min_fruit_count === 1000){
		  return -1;
	   }
	   return min_fruit_type;
	}

   function find_fruit(x, y){
	   var min_fruit_type = get_min_type();
	   if(min_fruit_type === -1){
		  return PASS;
	   }
	   var board = get_board();
	   
	   if(nearest_fruit_location_x != -5555){
		   var board = get_board();
		   if(board[nearest_fruit_location_x][nearest_fruit_location_y] > 0){
			  //find path to nearest fruit
			  return find_path([cur_location_x, cur_location_y],[nearest_fruit_location_x, nearest_fruit_location_y]);
		   }else{
			  //fruit has been taken by the opponent, reset variables and look for nearest fruit
			  nearest_fruit_location_x = -5555;
			  nearest_fruit_location_y = -5555;
			  nearest_fruit_distance = 100000;
		   }
	   }
	   var adjacent_squares = [ 
							[x-1, y], [x-1, y+1], [x, y+1], [x+1, y+1],
							[x+1, y], [x+1, y-1], [x, y-1], [x-1, y-1]
						  ];
		for(var ctr=0; ctr < 8; ctr++){
		   var tempx = adjacent_squares[ctr][0];
		   var tempy = adjacent_squares[ctr][1];
		   //check if square is out of board
		   if(tempx < 0 || tempx > WIDTH-1 || tempy < 0 || tempy > HEIGHT-1){
			  continue;
		   }
		   //store for expansion in search of fruit
		   if(open_squares_grid[adjacent_squares[ctr][1]][adjacent_squares[ctr][0]] != MARKED_FOR_EXPAND){
			  open_squares_grid[adjacent_squares[ctr][1]][adjacent_squares[ctr][0]] = MARKED_FOR_EXPAND;
			  open_squares[open_squares.length] = [adjacent_squares[ctr][0], adjacent_squares[ctr][1]];
		   }
		   //test current adjacent square for presence of fruit, if it hasn't been tested
		   if(checked_squares[adjacent_squares[ctr][1]][adjacent_squares[ctr][0]] != CHECKED){
			  //mark square as checked for fruit
			  checked_squares[adjacent_squares[ctr][1]][adjacent_squares[ctr][0]] = CHECKED;
			  var is_fruit = fruit_exists(adjacent_squares[ctr][0], adjacent_squares[ctr][1]);
			  if(is_fruit && board[adjacent_squares[ctr][0]][adjacent_squares[ctr][1]] === min_fruit_type){	  
				 var distance_to_fruit = Math.round(10 * Math.sqrt(Math.pow(adjacent_squares[ctr][0] - cur_location_x, 2) + Math.pow(adjacent_squares[ctr][1] - cur_location_y, 2)));
				 if(distance_to_fruit < nearest_fruit_distance){
					nearest_fruit_location_x = adjacent_squares[ctr][0];
					nearest_fruit_location_y = adjacent_squares[ctr][1];
					nearest_fruit_distance = distance_to_fruit;
				 }
			  }  
		   }
		}
		if(nearest_fruit_location_x != -5555){
		   //find path to nearest fruit
		   return find_path([cur_location_x, cur_location_y],[nearest_fruit_location_x, nearest_fruit_location_y]);
		}else{
		   //no fruit in the adjacent squares. expand search using the next node in open_square
		   square = open_squares.shift();
		   return find_fruit(square[0], square[1]);
		}
	}

   function find_path(src, dest){
	   var adj_squares = [ 
							[src[0]-1, src[1]], [src[0]-1, src[1]+1], [src[0], src[1]+1], [src[0]+1, src[1]+1],
							[src[0]+1, src[1]], [src[0]+1, src[1]-1], [src[0], src[1]-1], [src[0]-1, src[1]-1]
						  ];
	   //find the adjacent square with the least distance to destination. return move
	   var min_distance = 500000;
	   var direction = null;
	   for(var ctr=0; ctr<8; ctr++){
		  var distance_to_fruit = Math.round(10 * Math.sqrt(Math.pow(adj_squares[ctr][0] - dest[0], 2) + Math.pow(adj_squares[ctr][1] - dest[1], 2)));
		  
		  if(distance_to_fruit < min_distance){
			 min_distance = distance_to_fruit;
			 if(adj_squares[ctr][0] === src[0]-1){
				direction = WEST;
			 }
				if(adj_squares[ctr][0] === src[0]+1){
				direction = EAST;
			 }
			 if(adj_squares[ctr][0] === src[0]){
				switch(adj_squares[ctr][1]){
				   case src[1]+1:
					  direction = SOUTH;break;
				   case src[1]-1:
					  direction = NORTH;break;
				}
			 }
		  }
	   }
	   return direction;
	}

   function fruit_exists(x, y){
	   if(x < 0 || x > WIDTH-1 || y < 0 || y > HEIGHT-1){
		  return false;
	   }
	   var board = get_board();
	   if (board[x][y] > 0) {
		   return true;
	   }
	   return false;
	}

   //initialize arrays for keeping track of squares 
   //that have already been checked for fruit and for expanding search
   function init_arrays(){
	   for(var row = 0; row < HEIGHT; row++){
		  checked_squares[row] = new Array(WIDTH);
		  open_squares_grid[row] = new Array(WIDTH);
		  for(var col = 0; col < WIDTH; col++){
			 checked_squares[row][col] = -1;
			 open_squares_grid[row][col] = -1;
		  }
	   }
	}
	
	return{
	   init_arrays: init_arrays,
	   find_fruit: find_fruit
	};
})();